% Chapter X

\chapter{Conclusion \& Future work} % Chapter title
\label{ch:conclandfutwrk} % For referencing the chapter elsewhere, use \autoref{ch:name} 

% 3-5 Pages maximum.
%----------------------------------------------------------------------------------------

\section{Conclusion}
\label{sec:conc}

The problem of allocating agents to tasks having a precise collocation is space is a recurrent problem in collective robotics.

In environmental monitoring, for instance, we may observe the problem of having robots deployed in an unknown environment in order to check for the presence of dangerous substances.
Generally, the size and the morphology of the environment prevents the robots from having a global communication and from sharing knowledge about the environment.
Hence, each robot needs to rely only on its own capabilities or eventually, communicate with the neighboring robots.
Clearly, a centralized solution is technically unfeasible and presents several disadvantages: \emph{single point of failure} and \emph{lack of scalability} among all.
Thus, devising a distributed method, possibly emerging from the local coordination among the agents becomes the only possible solution.

Our research question mainly arises from the need of finding efficient solutions to such problems.

In this thesis, we consider a specific instance of the problem of allocating robots to spatially distributed tasks, by fixing some constraints.
In our vision of the problem, we have a finite number of robots ($n$) and a finite number of tasks $m$, with $n<m$.
The tasks are distributed in space according to precise circular patterns, denominated clusters.
Each cluster is characterized by the number of tasks it is composed of (i.e. the cluster request) and the number of robots currently being allocated to tasks belonging to the cluster (i.e. the cluster occupation).
The robots, on the other hand, are homogeneous agents, with a minimal set of sensors, endowed with local sensing and local communication capabilities.

To the best of our knowledge, we are not aware of other studies in the literature that try to solve a similar problem. 
For this reason, we developed the \emph{Naive} method to serve as a baseline for comparison with our main contributions: the \emph{Probabilistic} and \emph{Informed} one.
We have decomposed the spatial allocation problem into two distinct sub-problems, to be tackled independently and sequentially: \emph{task localization} and \emph{task allocation}.
Each method is characterized by a different strategy to solve the aforementioned subproblems.

The \emph{Naive} method simply consists of a random exploration of the environment to find the tasks and a greedy allocation to them as soon as they are detected.

The \emph{Probabilistic} method maintains the uninformed random walk from the \emph{Naive} method as exploration technique, but substitutes the purely deterministic allocation rule with a probabilistic decision mechanism.
Here, the probability of leaving a cluster to further explore the environment is proportional to the cluster occupation.
The use of this stochastic decision mechanism should in principle, favor the redistribution of the robots across the clusters, yielding to a more uniform distribution.
Moreover, a check on the occurrence of a stalemate, a situation that may occur when two robots decide to allocate to the same task, has been introduced, along with a probabilistic decision mechanism to overcome this issue and increase the number of allocated robots.

The \emph{Informed} method is built upon the \emph{Probabilistic} one, preserving the probabilistic allocation mechanism but upgrading the uninformed random walk to an informed one through the use of odometry.
Odometry is introduced to prevent multiple visits to clusters whose occupation corresponds to the request (i.e not requiring additional robot to be allocated).

We decided to evaluate the performances of our methods with respect to two relevant aspects: \emph{allocation uniformity} and \emph{allocation speed}. 

In order to do so, we devised three scenarios: \emph{Uniform}, \emph{Biased} and \emph{Corridor}.
Each one of them is characterized by the disposition of the clusters in space and the positioning of the area where the robots are initially deployed.

The \emph{Uniform} one has a central deployment area which is equally distant from all the clusters in the environment, while the \emph{Biased} one presents some clusters closer to the deployment zone than the others.
The \emph{Corridor} one consists of a narrow arena, with the clusters linearly deployed in the middle of it.

Concerning \emph{allocation uniformity}, the \emph{Informed} method performs better than the \emph{Naive} and \emph{Probabilistic} one on all the designed scenarios.
However, no method is able to reach the ideal uniform allocation on any of the scenarios.
Regarding \emph{allocation speed}, the \emph{Naive} method achieves a faster robot allocation than the \emph{Probabilistic} and the \emph{Informed} one on scenario \emph{Uniform} and \emph{Biased}, but it is outperformed by both of them on the \emph{Scenario C}.
Furthermore, we observed that there exist a trade-off between the two aspects we are interested in, (i.e. a fast allocation comes at the expense of evenness in the distribution of robots and viceversa).
Our analysis showed that the Informed \emph{method} is the one achieving the better balance between \emph{uniformity} and \emph{velocity}.

We also devised a metric to assess the difficulty of a scenario with respect to the problem of achieving a uniform allocation.
In fact, by looking at the number of times that every cluster is seen by the robots, we are able to determine whether the distribution of this views is even across cluster or it is biased towards certain ones.
In the latter case, we can safely assume that the scenario is more difficult since the applied method has to compensate for the differences in the views repartitions. 
 
To summarize, our contribution consists of three methods to achieve the allocation of robots to tasks distributed in space and aggregated in clusters.
In terms of relative performances among the methods, the \emph{Naive} method is the one achieving the fastest allocation while the \emph{Informed} one allows to better distribute the robots across the clusters.
Nevertheless, there is a strong influence of the type of scenario on the performance of the system.

%----------------------------------------------------------------------------------------

\section{Future work}
Since the development and test of the methods has occurred only by means of simulation, our plan is to run experiments using the real \emph{e-puck} robots and the real \emph{TAM}s.

Even though the error in the odometry has been modeled and no communication is employed, further studies to verify the impact of the real noise on the swarm performance should be performed.

Another interesting possibility would be to evaluate different probabilistic rules for the allocation of the robots, in order to have a more fine-grained control on the distribution of the robots across clusters.

A further study that could be made concerns the use of an inter-cluster recruiting behavior, as occurring in some species of ants, to direct robots from a cluster to another.

Last but not least, tests on the flexibility (i.e. the capacity of the swarm to dynamically adapt to changes in the response), scalability with respect to the number of tasks and robots and robustness of the methods with respect to faults should necessarily be performed.
